Conventionally, representative authentication methods include a user authentication scheme for checking the authenticity of a system user, a message authentication scheme for proving that a message is an authentic one, and a digital signature scheme in which they are combined further and the information producer guarantees that a produced message is authentic. Here, the user authentication scheme, the message authentication scheme, and the digital signature scheme will be briefly explained with references to the respective figures.
FIG. 1A is a conceptual diagram of an authentication scheme according to the Fiat Shamir scheme which is a representative example of the user authentication scheme. (A. Fiat and A. Shamir: "How To Prove Yourself, Practical Solutions To Identification And Signature Problems", Proc. of Crypto '86, 1986.5, and U.S. Pat. No. 4,748,668.
According to this Fiat Shamir scheme, when a party (referred to hereafter as a prover) which owns secret information s tries to prove its authenticity to a verifier, it is authenticated as follows, with N (=pq: p and q are mutually different large prime numbers) and I(=s.sup.2 (mod N)) as the public information of the prover, and s, p and q as the secret information of the prover.
First, at the beginning, the prover generates a random number R, calculates a preresponsive message X.dbd.R.sup.2 (mod N), and sends X to the verifier. The verifier who received X selects 0 or 1 randomly as a check bit e, and sends e to the prover. The prover who received e calculates a responsive message Y.dbd.Rs.sup.e (mod N), and sends Y to the verifier. The prover who received Y verifies whether a verification formula Y.sup.2 .dbd.X.times.I.sup.e (mod N) holds.
By referring to the foregoing steps as one round, and repeating this for t rounds, the probability of a third party who does not know the secret information clearing the verification formula of the verifier becomes (1/2.sup.t). Therefore, when the authentication is cleared for sufficiently large t, the verifier may very well judge that the verification target (prover) is an authentic prover who owns the secret information s.
Here, this authentication scheme is generally referred as an authentication scheme based on the zero knowledge interactive proof, which has merit in that the prover notifies only a fact that it owns the secret information s to the verifier, without leaking other contents related to the secret information s.
In the Fiat Shamir scheme, there has been a problem that the log for the prover and the verifier cannot be used later as definitive evidence that the verifier has authenticated the prover. For this reason, there is a proposition of an authentication scheme in Sakurai (Japanese Patent Application Laid Open No. 5-12321) as a solution for this problem. According to this authentication scheme, it is said that, definitive evidence that the verifier has really authenticated the prover remains even after the verifier has authenticated the prover.
What remains as an evidence though is only that the verifier authenticated the prover through a communication at best, and apart from this authenticated fact, it does not refer to what kind of communication has been made, such as the communication content in the first place. Also, because it records and maintains all the communication sequences as the evidence of the authenticated fact, there is also a drawback in that a large amount of information must be recorded and maintained by the verifier.
Next, FIG. 1B is a conceptual diagram of an authenticator in which the prover, who wishes to transmit a message M, produces an authenticator h.sub.k (M) for the message M by utilizing the hash function h with a secret key K.sub.h as a parameter. The prover transmits the authenticator along with the message M to the verifier who is a transmission target. The verifier is secretly sharing the same secret key K.sub.h as the prover in advance, so that it produces the authenticator by using the secret key K.sub.h from the received message similarly as in the above, and checks by matching with the received authenticator. When this matching succeeds, the authenticity of the received message is guaranteed. Because the correct authenticator for an arbitrary message cannot be produced without knowing the secret key K.sub.h.
The main purpose of both the above described user authentication and message authenticated schemes is preventing an illegal act by a third party. The user authentication scheme verifies, at best, that the prover is an authenticated owner of the secret information. In other words, it proves that a third party has not been using that secret information illegally. The message authenticated scheme verifies only that an illegal act by a third party, such as an alteration of the message, has not been performed. Therefore, these two authentication schemes are effective, in principle, only against an illegal act by a third party. Their lack of effectiveness against illegal acts by the prover or the verifier is a draw back.
Next, FIG. 1C is a conceptual diagram of an RSA signature scheme (R. L. Rivest, A. Shamir, L. Adleman, "A Method For Obtaining Digital Signatures And Public-Key Cryptosystem", Comm. ACM, vol. 21, No. 2, 1978.2) which is one example of a digital signature.
According to the RSA signature scheme, it is authenticated as follows, with e and N (=pq: p and q are mutually different large prime numbers) as the public information of the signer, and d[e.times.d (mod(p-1) (q-1))=1], p and q as the secret information of the signer.
First, the signer calculates a signed message C=M.sup.d (mod N) in order to guarantee that the message M is certainly what is produced by the signer, and transmits C to the verifier. The verifier who received the signed message C calculates M=C.sup.e (mod N), and judges the authenticity of the obtained message M. At this point, when it is judged that the obtained message M is authentic, it is guaranteed that the received message M is definitely what was produced by the signer.
This is because a correct signed message for an arbitrary message cannot be produced without knowing the secret information d, and in addition, the secret information d is unique to each individual so that the signer himself is also going to be specified. Therefore, illegal acts in which the third party or the verifier alters the message content, or the signer denies the message content, are considered to be difficult.
However, at best, this only has an effect from the point at which the exchange of the messages has normally finished. There is no guarantee for what came before that, i.e., whether the transmitted signed message C has surely reached the verifier from the viewpoint of the signer. As such, so that once it is claimed that the signed message C has not been received by the verifier, there is no means for the signer to oppose that claim, which is a drawback.
In a case in which the information provider provides a message requested by the user, it is necessary to satisfy the following four conditions:
(1) the user authentication for guaranteeing that it is the authentic user;
(2) the delivery proof for guaranteeing that the information provider has surely provided the message requested by the user, and the user has received the provided message;
(3) the content proof that the provided message is the authentic one, which is capable of preventing the illegal act such as the alteration; and
(4) the fact that all of (1) to (3) can be proved later on as the information provider presents evidence such as a log, and the like to an arbitrator, as needed or desired.
As explained in the conventional schemes, the Fiat Shamir scheme satisfies (1) alone, the scheme of Sakurai (Japanese Patent Application Laid Open No. 5-12321) satisfies only (1) and a part of (4) (only an evidence for the user authentication), the message authentication satisfies only a part of (3) (only a guarantee that the message is authentic), and the RSA signature scheme satisfies only (3), so that there has been a drawback that the information provider is not provided evidence of some kind of illegal act, such as an improper claim in which the user says the provider message has not been received despite the fact that it has been received, as in (2) in particular.